/****************************************************
          File Name:array_string.h
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: Tue 10 Feb 2015 04:04:57 PM CST
*****************************************************/

#ifndef array_string_h_
#define array_string_h_

#include <stdlib.h>

typedef string char *;

void StrAssign(string T, const char *s)
{
    register int i;
    for(i=0; s[i]!='\0'; i++);
    T = (string)malloc(i);
    for(;i!=0; i--)
        T[i] = s[i];
}

bool StrCopy(string T, string S)
{
    if(S[0] == '\0') return false;

    register int i;
    for(i=0; S[i]!='\0'; i++);
    T = (string)malloc(i);
    for(;*S !=i 0;)
        *T++ = *S++;
    return true;
}

void ClearString(string S)
{
    for(; *S++ !='\0';)
        *S = '\0';
}

bool isEmpty(string S)
{
    for(; *S != '\0'; S++)
        if(*S != '\0')
            return false;
    return true;
}

int StrLength(string s)
{
    int res = 0;
    for(;*S++ != '\0')
        res++;

    return res;
}

int StrCompare(string S, string T)
{
    for(; *S++ !='\0' && *T++ !='\0';)     // len(S) == len(T)
    {
        if(*S < *T)
            return -1;
        else if(*S > *T)
            return 1;
        else
            continue;
    }
    S = S -1;
    T = T -1;
    if(*S > *T)                 // len(S) > len(T)
        return 1;
    else if(*S < *T)            // len(S) < len(T)
        return -1;

    return 0;
}

void Concat(string T, string S1, string S2)
{
    register int i, j, k;
    bool mark = false;

    for(;*S1++ !='\0' && *S2++ != '\0';)
        i++;
    if(*S1 == '\0')
    {
        mark = true;
        for(j=i; *S2[j] !='\0'; j++);
    }
    else if(*S2 == '\0')
        for(j=i; *S1[j] != '\0'; j++);

    j = j + i;  // max(len(S1), len(S2))
    k = j + i;      // len(T) = len(S1) + len(S2)
    T = (string)malloc(k);

    if(mark)  // len(S1) < len(S2)
    {
        for(;i--;)
            T[i] = S1[i];   // assign S1 to T

        for(; k != i; k--)
            T[k] = S2[k];   // assign S2 to T
    }
    else    // len(S1) > len(S2)
    {
        for(;j--;)
            T[j] = S1[j];   // assign S1 to T
        
        for(; k != j; k--)
            T[k] = S2[k];
    }
}

int SubString(string Sub, string S, int pos, int len)
{
    register int i;

    if(isEmpty(S)) return -1;           // S is empty
    for(i=0; S[i]!='\0'; i++);
    if(pos < 1 || pos > i)
        return -2;                      // position out of range
    if(len < 0 || len > (i - pos + 1))
        return -3;                      // substring out of range

    Sub = (string)malloc(len);
    for(i=0; len--; i++)
        Sub[i] = S[pos+i];

    return 0;
}

int IndexNaive(string S, string T, int pos)      // naive-string-matcher
{
    register int n=0, m=0, i, j, equal;
    if(!S && S[0]=='\0') return false;
    if(!T && T[0]=='\0') return false;
    for(;S[n];n++);
    for(;T[m];m++);
    if(pos < 0 || pos > n) return false;

    for(i = pos; i <= n-m; i++)
    {
        equal = 1;
        for(j=0; equal && j<m; j++)
            if(T[j] != S[i+j])
                equal = 0;
        if(equal) break;         // find
    }
    if(equal)
        return i;
    else return 0;    
}

void Replace(string S, string T , string V)
{
    char *res;
    register int i, j, k, m;
    int len, lv, ls, lt, tmp = 0, re = -1; // Indexnaive return -1 when not match

    ls = StrLength(S);
    lt = StrLength(T);
    lv = StrLength(V);

    int pos[ls -lt];        // space for speed;

    for(i=0;; i++, re++)
    {
        re = IndexNaive(S, T, re);
        pos[i] = re;
        if(tmp == re || re == -1) break;
        tmp = pos[i];
    }

    i = 0;
    if(pos[0] != -1)
    {
        len = ls + i*(lv - lt);  // get replaced string's length
        if(!(res = (string)malloc(len))) abort();

        for(m=0, j=0; j < len; j++, m++)
        {
            res[j] = S[m];
            if(pos[i] && (j == pos[i]))
            {
                for(k=0; k<lv; k++)
                    res[j] = V[k];
                i++;
                m += lt;
                pos[i] += i*(lv -lt);   // re-calculate postion
            }
        }
        free(S);
        S = res;                // S point to res;
    }
}

void StrInsert(string S, int pos, string T)
{
    if(!S && S[0]=='\0') return false;
    if(!T && T[0]=='\0') return false;
    ls = StrLength(S);
    lt = StrLength(T);
    if(pos < 0 || pos > ls) return false;

    string tmp;

    if(!(tmp = (string)malloc(ls + lt))) abort();
   for(; *S != S[pos];)
      *tmp++ = *S++;
   for(; *T != '\0';)
       *tmp++ = *T++;
   for(; *S != '\0';)
       *tmp++ = *S++;
   free(S);
   S = tmp;
}

void StrDelete(string S, int pos, int len)
{
    if(!S && S[0]=='\0') return false;
    ls = StrLength(S);
    if(pos < 0 || pos > ls-len-1) return false;

    string tmp = S;
    register int i;
    S += pos;
    for(i = 0; i < len; i++ )
        *(S + pos +i) = *(S + len + i);
    S = tmp;
    S[ls -len] = '\0';
}
